package Algorithm.dynamicProgramming.introduct;

/**
 * 62. 不同路径 https://leetcode.cn/problems/unique-paths
 * 题目简述：一个机器人位于一个m x n网格的左上角。机器人每次只能向下或者向右移动一步。机器人到达网格的右下角总共有多少条不同的路径？
 */
public class UniquePaths {

    /**
     * 动态规划
     * 1. 定义dp：dp[i][j]为到达坐标(i,j)的格子的路径数
     * 2. 确定递推公式：格子(i,j)只能由上方的格子(i-1,j)或者左边的格子(i,j-1)走来，故dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * 3. 初始化dp: 第一行和第一列的格子路径数均为1
     * 4. 遍历方式：从(1, 1)开始从上往下逐行遍历
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i < m;i++) {
            dp[i][0] = 1;
        }
        for(int j=1;j < n;j++) {
            dp[0][j] = 1;
        }
        for(int i=1;i < m;i++) {
            for(int j=1;j < n;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
